package 排序算法.快速排序;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 排序.快速排序
 * @ClassName: t215
 * @Author: zhouyihe
 * @Date: 2025/11/5 16:54
 * @Description: 数组中第k大的数
 */
public class t215 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(findKthLargest(arr, k));
    }

    public static int findKthLargest(int[] nums, int k) {

        return quickSort(nums, 0, nums.length - 1,k );
    }

    public static int quickSort(int[] arr, int low, int high, int k) {
        if (low == high) return arr[low];
        int i = low;
        int j = high;
        int key = arr[low];
        while (i < j) {
            while (i < j && key <= arr[j])
                j--;
            if ((i < j)) {
                arr[i++] = arr[j];
            }
            while (i < j && key > arr[i])
                i++;
            if (i < j) {
                arr[j--] = arr[i];
            }
        }

        arr[i] = key;
        if (i == arr.length - k) {
            return arr[i];
        } else if (i > arr.length - k) {
            return quickSort(arr, low, i - 1, k);
        } else {
            return quickSort(arr, i + 1, high, k);
        }

    }
}
